Graph Coloring with Adaptive Evolutionary Algorithms

This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EAs). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping Genetic Algorithm (GGA) on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping (GA) and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.     

提前还贷及其隐含期权的分析

可提前还款的定期贷款是隐含着期权的利率衍生物，本文建立CIR利率模型下可提前还款的定期贷款的数学模型，通过离散偏微分方程，建立了模型的计算方法，讨论了随机利率对提前还贷的影响．     

Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function

The paper present a linear-time algorithm for solving the two machine open shop scheduling problem to minimize an arbitrary regular penalty function depending on the lengths of periods during which the machines are used. Both the preemptive and the nonpreemptive cases of the problem are considered.     

Equality and inequality constrained optimization algorithms with convergent stepsizes

In this paper, we consider two algorithms for nonlinear equality and inequality constrained optimization. Both algorithms utilize stepsize strategies based on differentiable penalty functions and quadratic programming subproblems. The essential difference between the algorithms is in the stepsize strategies used. The objective function in the quadratic subproblem includes a linear term that is dependent on the penalty functions. The quadratic objective function utilizes an approximate Hessian of the Lagrangian augmented by the penalty functions. In this approximation, it is possible to ignore the second-derivative terms arising from the constraints in the penalty functions.The penalty parameter is determined using a strategy, slightly different for each algorithm, that ensures boundedness as well as a descent property. In particular, the boundedness follows as the strategy is always satisfied for finite values of the parameter.These properties are utilized to establish global convergence and the condition under which unit stepsizes are achieved. There is also a compatibility between the quadratic objective function and the stepsize strategy to ensure the consistency of the properties for unit steps and subsequent convergence rates.This research was funded by SERC and ESRC research contracts. The author is grateful to Professors Laurence Dixon and David Mayne for their comments. The numerical results in the paper were obtained using a program written by Mr. Robin Becker.     

Discrete linear bilevel programming problem

In this paper, we analyze some properties of the discrete linear bilevel program for different discretizations of the set of variables. We study the geometry of the feasible set and discuss the existence of an optimal solution. We also establish equivalences between different classes of discrete linear bilevel programs and particular linear multilevel programming problems. These equivalences are based on concave penalty functions and can be used to design penalty function methods for the solution of discrete linear bilevel programs.Support of this work has been provided by the INIC (Portugal) under Contract 89/EXA/5, by INVOTAN, FLAD, and CCLA (Portugal), and by FCAR (Québec), NSERC, and DND-ARP (Canada).     

A new general-purpose least-squares finite element model for steady incompressible low-viscosity laminar flow using isoparametric C1-continuous Hermite elements

This paper deals with a critical evaluation of various finite element models for low-viscosity laminar incompressible flow in geometrically complex domains. These models use Galerkin weighted residuals UVP, continuous penalty, discrete penalty and least-squares procedures. The model evaluations are based on the use of appropriate tensor product Lagrange and simplex quadratic triangular elements and a newly developed isoparametric Hermite element. All of the described models produce very accurate results for horizontal flows. In vertical flow domains, however, two different cases can be recognized. Downward flows, i.e. when the gravitational force is in the direction of the flow, usually do not present any special problem. In contrast, laminar flow of low-viscosity Newtonian fluids where the gravitational force is acting in the direction opposite to the flow presents a difficult case. We show that only by using the least-squares method in conjunction with C¹-continuous Hermite elements can this type of laminar flow be modelled accurately. The problem of smooth isoparametric mapping of C¹ Hermite elements, which is necessary in dealing with geometrically complicated domains, is tackled by means of an auxiliary optimization procedure. We conclude that the least-squares method in combination with isoparmetric Hermite elements offers a new general-purpose modelling technique which can accurately simulate all types of low-viscosity incompressible laminar flow in complex domains.     

Solving two-Level variational inequality

An approach to solving a mathematical program with variational inequality or nonlinear complementarity constraints is presented. It consists in a variational re-formulation of the optimization criterion and looking for a solution of thus obtained variational inequality among the points satisfying the initial variational constraints.This research was supported by the Russian Fundamental Research Foundation, Grant No. 93-012-842     

On the entropic perturbation and exponential penalty methods for linear programming

This note points out that the recently proposed exponential penalty approach to linear programming is identical to the well-known entropic perturbation approach. The primal and dual trajectories provided by these two approaches are shown to be equivalent.The work of the first author was supported partially by the North Carolina Supercomputing Center and 1995 Cray Research Grant.     

Assessing the Error Probability of the Model Selection Test

The asymptotic error probability of Linhart's model selection test isevaluated, and compared with the nominal significance level. We examine thecase where the expected discrepancies of the candidate models from the truemodel are asymptotically equal. The local alternatives method is employed inthe limiting operation of the asymptotic evaluation. Although the errorprobability under the null hypothesis is actually shown to be equal to orless than the level for most situations, intolerable violations of the errorcontrol are observed for nested models: It is often erroneously concludedthat the smaller model is significantly better than the larger model. Toprevent this violation, a modification of Linhart's test statistic isproposed. The effectiveness of the proposed test is confirmed throughtheoretical analysis and numerical simulations.